package cn.z2huo.demo.spring.webmvc.csv;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <p>
 *
 * @author z2huo
 */
class Solution {

    /**
     * <p>暴力破解
     *
     * <p>三个 for 循环遍历，找无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        if (s == null || s.isEmpty()) {
            return result;
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String subStr = s.substring(i, j - 1);
                String repeatStr = s.substring(j - 1, j);
                if (subStr.contains(repeatStr)) {
                    // 当某个子串中的最后一个字符在子串中重复时，跳过当前循环
                    break;
                } else {
                    // 如果不重复时，将 result 和 j-i 中更大的赋值给 result，相当于更新了不重复子串的最大长度
                    result = Math.max(j - i, result);
                }
            }
        }
        return result;
    }

    /**
     * <p>滑动窗口
     *
     * <p>优化掉暴力破解遍历过程中不需要重复判断的部分
     */
    public int lengthOfLongestSubstring2(String s) {
        int result = 0;
        if (s.length() == 1) {
            return 1;
        }
        for (int i = 0, j = 1; i < s.length() && j < s.length(); ) {
            // i 和 j 来确定窗口的起始位置和结束为止
            String subStr = s.substring(i, j);
            // judgeRepeatSingleStr 为待判断是否在窗口中有重复的字符
            String judgeRepeatSingleStr = s.substring(j, j + 1);
            int index = subStr.indexOf(judgeRepeatSingleStr);
            if (index != -1) {
                // 当有重复时，将 i 向后移动 index + 1，即窗口中出现重复的字符的下一个字符
                i = i + index + 1;
            } else {
                j++;
                result = Math.max(j - i, result);
            }
        }
        return result;
    }

    /**
     * <p>滑动窗口
     *
     * <p>优化掉暴力破解遍历过程中不需要重复判断的部分
     *
     * <p>优化版
     */
    public int lengthOfLongestSubstring3(String s) {
        int result = 0;
        int i = 0, j = 0;
        // set 用来存放窗口中的字符
        Set<Character> set = new HashSet<>();
        while (i < s.length() && j < s.length()) {
            // 当 set 中包含当前 j 遍历字符时，从 set 中移除 i 位置的字符，之后 i 增加，j 不变，直到 set 中没有当前 j 遍历的字符为止
            if (set.contains(s.charAt(j))) {
                set.remove(s.charAt(i++));
            } else {
                // 当 set 中不包含当前 j 遍历字符时，将该处的字符添加到 set 中，并更新 result 的值
                set.add(s.charAt(j++));
                result = Math.max(j - i, result);
            }
        }
        return result;
    }

    /**
     * <p>滑动窗口
     *
     * <p>使用 map 来存储字符及其位置
     */
    public int lengthOfLongestSubstring4(String s) {
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < s.length() && j < s.length(); j++) {
            char c = s.charAt(j);
            if (map.containsKey(c)) {
                // 如果 map 中包含当前字符，则窗口子串中有重复字符
                // 获取窗口中重复字符位置，将窗口左侧指针移动到重复字符的下一个位置
                // 这里需要处理从 map 中获取到了窗口外的元素的情况
                // 获取到窗口外的元素时，不需要重置窗口位置，比如遍历到 tmmzuxt 字符的第二个 t 时，会获取第一个 t 的位置
                i = Math.max(map.get(c) + 1, i);
            }
            // 将遍历元素及其位置存放到 map 中
            map.put(c, j);
            result = Math.max(j - i + 1, result);
        }
        return result;
    }

}
